1. The Field of the Invention
The present invention relates to wireless networks, and more specifically, to providing contention free quality of service to wireless stations.
2. Background and Relevant Art
Computer systems and related technology affect many aspects of society. Indeed, the computer system's ability to process information has transformed the way we live and work. Computer systems now commonly perform a host of tasks (e.g., word processing, scheduling, and database management) that prior to the advent of the computer system were performed manually. More recently, computer systems have been coupled to one another to form both wired and wireless computer networks over which the computer systems can communicate electronically to share data. As a result, many tasks performed at a computer system (e.g., voice communication, accessing electronic mail, electronic conferencing, web browsing) include electronic communication with one or more other computer systems via wired and/or wireless computer networks.
For example, a number of computer systems can be coupled to a data hub through corresponding wired connections (e.g., category 5 cable) to form a wired network (e.g., an Ethernet segment). Similarly, a number of wireless computer systems (commonly referred to as “stations”) can be coupled to a wireless access point (“AP”) through corresponding wireless connections (e.g., resulting from appropriate communication between radio transmitters and receivers) to form a wireless network (e.g., an IEEE 802.11 network). Further, a data hub and/or an AP can be connected to other data hubs, AP's, or other network devices, such as routers, gateways, and switches to form more complex networks (including both wired and wireless connections).
When computer systems communicate electronically, electronic data will often pass through a protocol stack that performs operations on the electronic data (e.g., packetizing, routing, flow control). The Open System Interconnect (“OSI”) model is an example of a networking framework for implementing a protocol stack. The OSI model breaks down the operations for transferring electronic data into seven distinct “layers,” each designated to perform certain operations in the data transfer process. While protocol stacks can potentially implement each of the layers, many protocol stacks implement only selective layers for use in transferring electronic data across a network.
When data is received from a network it enters the physical layer and is passed up to higher intermediate layers and then eventually received at an application layer. The physical layer, the lower most layer, is responsible for converting electrical impulses, light, or radio waves into a bit stream and vice versa. On the other hand, when data is transmitted from a computing system, it originates at the application layer and is passed down to intermediate lower layers and then onto a network. The application layer, the upper most layer, is responsible for supporting applications and end-user processes, such as, for example, electronic conferencing software, electronic mail clients, web browsers, etc.
An intermediate layer incorporated by most protocol stacks is the Data Link layer. The Data Link layer decodes data packets (received from higher layers) into bit streams for use by the physical layer and encodes bit steams (received from the physical layer) into data packets for use by higher layers. A sub-layer typically included in the Data Link layer is the Media Access Control (“MAC”) layer, which implements protocols for moving data packets onto a shared channel (e.g., an Ethernet segment or an IEEE 802.11-channel). Carrier Sense Multiple Access with Collision Detection (usually known as “CSMA/CD”) is a MAC layer protocol commonly used with wired Ethernet.
A computer system implementing a CSMA protocol senses a medium (e.g., a wired Ethernet segment) before transmitting data onto the medium. When the medium is sensed busy (i.e., when another computer system is transmitting), the computer system defers its transmission to a later time. On the other hand, when the medium sensed free the computer system is allowed to transmit. While CSMA protocols can be quite effective, there is always some chance that two (or more) computer systems simultaneously sense the medium as being free and transmit data at the same time. On wired Ethernet segments a collision is recognized by transmitting computer systems, which then go into a retransmission phase. During the retransmission phase, each transmitting computer system that detected a collision waits a random amount of time before attempting to retransmit (e.g., as part of on an exponential random backoff algorithm). This reduces the likelihood of the computer systems attempting to retransmit at the same time.
While these collision detection mechanisms are beneficial on wired networks, their usefulness on wireless networks is limited. This is due at least in part to there being no guarantee that all stations communicating with an AP are able to also communicate with each other. For example, a first wireless station may be physically located near the range limit of the AP and a second wireless station may be physically located 180 degrees from the first station also near the range limit of the AP. Accordingly, while both stations are within range of the AP they may be out of range of each other. Thus, there is a possibility that the first station detects a wireless channel as free when in fact the second station is transmitting data on the wireless channel. If the first station were to transmit data it would collide with the data from the second station resulting in corruption of data from both stations. Further, as the number of stations communicating with an AP increases, so does chance of collisions due to a number of stations being unable to communicate with each other.
Accordingly, computer systems on a wireless network may implement the Distributed Coordination Function (“DCF”) to attempt to reduce data collisions. DCF implements collision avoidance by requiring a station to sense a channel as being available for a DCF Inter Frame Space (“DIFS”) time (34 microseconds for 802.11a) plus a random interval of time. When a station senses that a wireless channel is free for DIFS plus the random interval, the station can transmit data. Typically, the random interval is varied among different stations. Thus, a station with a lower random interval may sense a wireless channel is free and begin to transmit data, before a station with a higher random interval senses the wireless channel. Further, even if some stations are configured with the same random interval, there is still a reduced chance that at any given time multiple stations having data to send will have the same random interval.
Some types of data, such as, for example, Voice over Internet Protocol (“IP”) and streaming video data, are time bounded. That is, if not delivered within a certain amount of time, the value of these types of data is reduced. For example, displaying ten frames of streaming video data every second (as opposed to 60 frames per second) would significantly degrade the usefulness of the streaming video data. On the other hand, other types of data, such as, for example, file transfer data and Web page data, have reduced time constraints. That is, delivery of these other types of data can tolerate some time delay without significantly affecting the usefulness of the data. For example, whether it takes 10 seconds or 20 seconds to present a Web page, the content of the Web page is still eventually presented. Accordingly, when time bounded data and data with reduced time constraints are both contending for media access, it may be appropriate to give preference to the time bounded data.
Unfortunately, DCF makes no distinction between different types of data and as such cannot give preference to particular types of data. Thus, each type of data equally contends with all other types of data for wireless medium access. Depending on DCF random intervals, data with reduced time constraints may be given access to a wireless medium before time bounded data. When data with reduced time constraints is given wireless medium access before time bounded data, the time bound data can be significantly degraded while providing little, if any, benefit to the data with reduced time constraints. Accordingly, some mechanisms have been developed to prioritize data and give a statistical preference to data based on the type of data.
Enhanced DCF (“EDCF”) is one mechanism for prioritizing and giving some preference to particular types of data. When an application is to send data, the application indicates a data priority to APIs that interface with the Data Link Layer. The APIs assign the data to one of eight queues, each corresponding to a particular priority. EDCF implements collision avoidance by requiring a station to sense a channel as being available for an Arbitration Inter Frame Space (“AIFS”) time plus a random interval of time. When a station senses that a wireless channel is free for AIFS plus the random interval, the station can transmit data. EDCF gives a statistical advantage to higher priority queues by assigning lower AIFS times to higher priority queues. Since higher priority queues have lower AIFS times, there is an increased chance of a higher priority queue at one station checking for wireless medium access (and being given access to the wireless medium) before a lower priority queue at another station.
Implementations of EDCF can assign time bounded data to higher priority queues, while assigning data with reduced time constraints to lower priority queues. Thus, higher priority data has an increased probability of being given wireless medium access before lower priority data. However, there is still some chance (due to the random time interval) that higher priority data at one station with have to contend with lower priority data at another station. That is, there is a chance that lower priority data will be given wireless medium access before higher priority data. Further, when two stations have data of the same priority, EDCF is essentially no different than DCF. Therefore systems, methods, and computer program products for providing contention free quality of service to time constrained data would be advantageous.